package 中等.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中
 * firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。
 * 每个区间列表都是成对 不相交 的，并且 已经排序 。
 * 返回这 两个区间列表的交集 。
 * 形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
 * 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/interval-list-intersections
 */
public class 区间列表的交集_986 {

    public static void main(String[] args) {

        for (int[] ints : intervalIntersection(new int[][]{{6, 7}, {8, 13}, {15, 19}},
                new int[][]{{1, 2}, {4, 5}, {11, 13}, {15, 16}, {17, 19}})) {
            System.out.println(Arrays.toString(ints));
        }

    }

    /**
     * 双指针+分类讨论
     * 1，如果 secondList[sIdx][1] < firstList[fIdx][0] 或者
     * firstList[fIdx][1] < secondList[sIdx][0]，说明
     * 两个区间没有交集，区间最大值较小的区间排除
     * 2，否则表示两个区间有交集，交集右端点为，两区间右端点较小
     * 的值，交集左端点为两区间左端点较大的值，同样区间最大值较小的区间排除
     */
    public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> list = new ArrayList<>();
        int fIdx = 0, sIdx = 0;
        while (fIdx < firstList.length && sIdx < secondList.length) {
            boolean flag = false;
            while (!flag) {
                flag = true;
                while (fIdx < firstList.length && sIdx < secondList.length &&
                        firstList[fIdx][1] < secondList[sIdx][0]) {
                    fIdx++;
                    flag = false;
                }
                while (sIdx < secondList.length && fIdx < firstList.length &&
                        secondList[sIdx][1] < firstList[fIdx][0]) {
                    sIdx++;
                    flag = false;
                }
            }

            if (fIdx == firstList.length || sIdx == secondList.length) break;

            if (firstList[fIdx][1] == secondList[sIdx][1]) {
                list.add(new int[]{Math.max(firstList[fIdx][0], secondList[sIdx][0]), firstList[fIdx][1]});
                fIdx++;
                sIdx++;
            } else if (firstList[fIdx][1] > secondList[sIdx][1]) {
                list.add(new int[]{Math.max(firstList[fIdx][0], secondList[sIdx][0]), secondList[sIdx][1]});
                sIdx++;
            } else {
                list.add(new int[]{Math.max(firstList[fIdx][0], secondList[sIdx][0]), firstList[fIdx][1],});
                fIdx++;
            }
        }

        return list.toArray(new int[list.size()][2]);
    }

}
